/*
Date:20210411 0:16pm
*/
class Solution {
public:
    bool dongtai(string& s, string& p, int i,int j)
    {
        //双方都还有字符
        if(i>-1&&j>-1)
        {
            if(p[j]=='*')
            {
                //如果是a和a*这种情况，就从a消失和a*消失里挑一个，有一个最后能成功就算成功，因此是或。
                if(p[j-1]==s[i]||p[j-1]=='.')
                {
                    return (dongtai(s, p, i-1, j)||dongtai(s, p, i, j-2));
                }
                else
                {//如果是b和a*这种情况，就a*消失
                    return dongtai(s, p, i, j-2);
                }
            }
            else
            {//不是*就只能是字符了，要注意还有可能是'.'。
                if(s[i]==p[j]||p[j]=='.')
                {
                    return dongtai(s, p, i-1, j-1);
                }
                //还不是就不匹配了
                else
                {
                    return false;
                }
            }
        }
        else
        {
            //都没字符了，即检查过的地方都没问题。
            if(j<0&&i<0)
            {
                return true;
            }
            return false;
        }

    }
    bool isMatch(string s, string p) {
        //当做哨兵以免给空的字符串。我的函数处理不了空的。
        s.insert(s.begin(),'a');
        p.insert(p.begin(),'a');
        return dongtai(s,p, s.size()-1,p.size()-1);
    }
} ;